//
// Created by Lenovo on 2021/12/14.
//

#include "SqList.h"

Status InitList_Sq(SqList* L){
    L->elem=(ElemType*) malloc(sizeof(ElemType)*LIST_INIT_SIZE);
    if(!L->elem) exit(MY_OVERFLOW);    //存储分配失败
    memset(L->elem,0, sizeof(ElemType)*L->list_size);   //若类型改变，此处初值需要自定义
    L->length=0;    //空表长为0
    L->list_size=LIST_INIT_SIZE;    //初始存储容量
    return OK;
}   //构造一个空的线性表


Status ListInsert_Sq(SqList* L,int i,ElemType e){
    //在顺序线性表中第i个位置前插入新元素e
    //i的合法值为1<=i<=L.length+1
    if(i<1||i>L->length+1) return ERROR;    //i值不合法
    if(L->length>=L->list_size){    //当前存储空间已满，增加分配
        ElemType * newBase= (ElemType *)realloc(L->elem,sizeof(ElemType)*(L->list_size+LIST_INCREMENT));
        if(!newBase) exit(MY_OVERFLOW);    //存储分配失败
        L->elem=newBase;    //新基址
        L->list_size+=LIST_INCREMENT;   //增加存储容量
    }
    ElemType *q=&L->elem[i-1];  //q为存储位置
    for (ElemType*p=&L->elem[L->length-1];p>=q;--p)     //插入位置及之后的元素右移
        *(p+1)=*p;
    *q=e;   //插入e
    L->length++;    //表长增加1
    return OK;
}    //再线性表的第i个元素处插入


ElemType ListDelete_Sq(SqList* L,int i){
    //在顺序线性表中删除第i个元素，并返回其值
    //i的合法值为1<=i<=L.length+1
    if(i<1||i>L->length) return ERROR;  //i值不合法
    ElemType *p=&L->elem[i-1];  //p为被删除元素的位置
    ElemType tmp=*p;    //被删除元素复制给tmp
    ElemType *q=L->elem+L->length-1;    //标尾的位置
    for (++p;p<=q;p++)  //被删除之后的元素左移
        *(p-1)=*p;
    L->length--;    //表长减一
    return tmp;
}   //删除线性表第i个元素


int LocateElem_Sq(const SqList *L,ElemType e,int(*compareSame)(ElemType e,ElemType f)){
    //在顺序线性表中查找第一个与值e满足compare（）关系的元素的位序
    //若找到，则返回其在L中的位置，否则返回0
    int i=1;    //i的初值为第1个元素的位序
    ElemType *p=L->elem;     //p的初值为第1个元素的存储位置
    while (i<=L->length&&!(*compareSame)(*p++,e)){i++;}
    if(i<=L->length) return i;
    else    return 0;
} //获取元素e在线性表中的位置（需要用户自定义元素比较函数）


void MergeList_Sq(const SqList *La,SqList Lb,SqList* Lc,int(*compareDifference)(ElemType e,ElemType f)){
    //已知顺序线性表La和Lb的元素按值非递减排列
    //归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列
    ElemType *pa=La->elem,*pb=Lb.elem;
    Lc->list_size=La->length+Lb.length;
    Lc->length=La->length+Lb.length;
    ElemType *pc=(ElemType*) malloc(sizeof(ElemType)*Lc->list_size);
    Lc->elem=pc;
    if(!Lc->elem) exit(MY_OVERFLOW);   //分配存储失败
    ElemType *pa_last=La->elem+La->length-1;
    ElemType *pb_last=Lb.elem+Lb.length-1;
    while (pa<=pa_last&&pb<=pb_last){   //归并
        if(compareDifference(*pa,*pb))
            *(pc++)=*(pa++);
        else
            *(pc++)=*(pb++);
    }
    while (pa<=pa_last) *(pc++)=*(pa++);    //插入La剩余元素
    while (pb<=pb_last) *(pc++)=*(pb++);    //插入Lb剩余元素
}  //将两个线性表合并


void ClearList_Sq(SqList *L){
    if(L==NULL) exit(ERROR);    //线性表不存在
    memset(L->elem,0, sizeof(ElemType)*L->length); //置空       //若类型改变，此处初值需要自定义
    L->length=0;
}   //将线性表置空


void DestroyList_Sq(SqList *L){
    if(L==NULL) exit(ERROR);    //线性表不存在
    ClearList_Sq(L);       //先清空
    free(L);    //释放表头结点
    L=NULL;
}    //销毁线性表


ElemType GetElem_Sq(const SqList *L,int i){
    if(i<1||i>L->length) exit(ERROR);  //i值不合法
    ElemType *p=&L->elem[i-1];   //线性表的第i个元素
    return *p;  //返回元素
}  //获取线性表中第i个元素


ElemType PriorElem_Sq(const SqList *L,ElemType cur_e,int(*compareSame)(ElemType e,ElemType f)){
    if(L->elem==NULL) exit(ERROR);   //线性表不存在
    int i=1;    //用来计数，保障不会越界访问
    ElemType *p=L->elem;     //线性表起始位置
    while (i<=L->length){      //逐个比较
        if(compareSame(*p,cur_e)&&p!=L->elem){   //在这个元素不是第一个元素的情况下
            return *(p-1);  //返回上一个元素
        }
        i++;
        p++;
    }
        return ERROR;   //未找到
}  //获取元素e的前一个元素


ElemType NextElem_Sq(const SqList *L,ElemType cur_e,int(*compareSame)(ElemType e,ElemType f)){
    if(L->elem==NULL) exit(ERROR);   //若线性表不存在
    int i=1;    //计数，保证不会越界访问
    ElemType *p=L->elem;     //线性表起始位置
    while (i<=L->length-1){      //逐个比较
        if(compareSame(*p,cur_e)&&p!=L->elem+L->length){  //在这个元素不是最后一个元素的情况下
            return *(p+1);  //返回下一个元素
        }
        i++;
        p++;
    }
    return ERROR;    //未找到
}   //获取元素e的后一个元素


void ListTraverse_Sq(SqList *L,void(*Visit)(ElemType)){
    if(L==NULL||L->elem==NULL) exit(ERROR);
    if(L->length==0) exit(EMPTY);
    ElemType *p=L->elem,*q=L->elem+L->length-1;    //p为线性表起始位置，q为线性表尾
    for (;p<=q;p++)    Visit(*p);
} //遍历线性表

Status ListPushBack_Sq(SqList *L,ElemType e){
    //在顺序线性表中最后位置前插入新元素e
    if(L->length>=L->list_size){    //当前存储空间已满，增加分配
        ElemType * newBase= (ElemType *)realloc(L->elem,sizeof(ElemType)*(L->list_size+LIST_INCREMENT));
        if(!newBase) exit(MY_OVERFLOW);    //存储分配失败
        L->elem=newBase;    //新基址
        L->list_size+=LIST_INCREMENT;   //增加存储容量
    }
    ElemType *q=&L->elem[L->length];  //q为存储位置;
    *q=e;   //插入e
    L->length++;    //表长增加1
    return OK;
}

